package com.sicheng.algorithm.recursive;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/8/28 14:10
 */
public class BinarySearch {
    public static void main(String[] args) {

        int[] arr = {1, 2, 3, 4, 4, 6, 7, 8, 9, 10};
        System.out.println(Arrays.toString(search(arr, 4)));
    }


    public static int[] search(int[] arr, int key) {
        if (arr == null || arr.length == 0)
            return new int[]{-1};
        return binarySearch(arr, 0, arr.length - 1, key);

    }

    /**
     * 参数说明
     *
     * @param arr   二分查找的数组
     * @param start 查找过程开始索引位置
     * @param end   查找过程结束索引位置
     * @param key   要查找的目标值
     * @return 返回的是目标的索引位置
     */
    public static int[] binarySearch(int[] arr, int start, int end, int key) {
        int mid = start + (end - start) / 2;
        if (key > arr[mid] && start < end)
            return binarySearch(arr, mid + 1, end, key);

        if (key < arr[mid] && start < end)
            return binarySearch(arr, start, mid - 1, key);
        if (key == arr[mid])
            return new int[]{mid};


        int n = 0;
        if (start > 0) {//如果进入此处，则key不存在
            for (int i = start; i < arr.length; i++) {
                if (arr[i] > arr[start - 1]) {
                    n = i;
                    break;
                }
            }
            return new int[]{start - 1, n};
        }


        return new int[]{};
    }
}
